НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №4 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Методи пошуку у масивах» Варіант № 16 Дата «02» травень 2022  Київ 2022 Мета: отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами, дослідження і вивчення методів пошуку ключових елементів у масивах, здійснення порівняння та аналізу ефективності використовуваних методів пошуку. Завдання до лабораторної роботи: Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом. / Рисунок 1 Теоретичні відомості: Сутність методу полягає в тому, що елементи масиву послідовно порівнюються зі зразком пошуку. Якщо має місце співпадання, то пошук закінчується. Інакше здійснюється перехід до наступного елементу. Отже, пошук припиняється або при досягненні кінця масиву, або при знаходженні заданого елемента. Оскільки наявність та місцезнаходження елементу наперед невідомі, то  для практичної реалізації алгоритму потрібно застосувати цикл з передумовою. Перевірку  знаходження елементу здійснимо за значенням змінної i, що є індексом поточного елементу масиву. Якщо значення цієї змінної перевищує n (кількість елементів масиву), то елемент не знайдений, а отже, в масиві відсутній.  Алгоритм простого пошуку запишемо у вигляді відповідної процедури. Метод пошуку з бар’єром. Перевагою методу простого пошуку  є його простота та наочність. Недоліком методу є те, що у заголовку циклу доводиться здійснювати дві перевірки: на допустимість індексу і на рівність значення. Якби ми знали, що шукане значення точно є десь у масиві, то першу перевірку можна було б не вказувати, що прискорило б пошук. Це наштовхує на думку, у вихідний масив потрібно тимчасово  включити шукане значення. Однак, оскільки розміри масиву змінені бути не можуть, включення можна здійснити на останнє місце масиву. Тоді  після завершення  пошуку потрібно повернути в кінець масиву початкове значення.  Для одержання  результату пошуку потрібно перевірити , чи дорівнює шукане значення тому елементові масиву, на якому відбулось завершення роботи алгоритму. Навіть, якщо елемент у початковому масиві був відсутній, і зупинка була здійснена на включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку. Наведений метод  називається “пошук елементу з бар'єром”. Роль бар’єрного елементу виконує включений в масив зразок пошуку. Включення повинно здійснюватись тільки замість останнього елементу масиву, після якого інших елементів немає. Пошук послідовності елементів в масиві Одне з найпростіших завдань пошуку інформації – пошук точно заданого підрядка у рядку. Проте, це завдання надзвичайно важливе – воно застосовується в текстових редакторах, СУБД, пошукових машинах тощо. Пошук рядка формально визначається в такий спосіб. Нехай заданий масив Т з N елементами і масив W з M елементами, причому 0 < M ≤ N. Пошук рядка виявляє перше входження W у Т, результатом будемо вважати індекс і, що вказує на перший з початку рядка (з початку масиву Т) збіг зі зразком (словом). Приклад 1. Потрібно знайти всі входження зразка W = abaa у тексті T = abcabaabcabca. / Рисунок 2 Відповідь: Зразок входить у текст тільки один раз, зі зсувом S = 3, індекс і =4. Хід роботи: Написано програмний код, який виконує 2 завдання: перше за методом барьерного пошуку, друге пошук послідовності в масиві. Для цього було створено два метода. Було проведено оцінку часової складності алгоритму та порівняно час роботи та кількість ітерацій з різною для різної кількості елемнтів матриці(10, 50, 100, 500). Оцінку часу роботи наведено нижче у вигляді таблиці та графіку. Було створенно метод для полегшення метода main, у ...